/*
https://leetcode-cn.com/problems/longest-duplicate-substring/solution/zui-chang-zhong-fu-zi-chuan-by-leetcode-0i9rd/
 */
import java.util.HashSet;
import java.util.Set;

public class Solution1044 {
    private static final int k1= 26;
    private static final int k2= 77;
    private static final int mod1=2027193890;
    private static final int mod2=1023000007;

    public String longestDupSubstring(String s) {
        int n=s.length();
        int[] arr=new int[n];
        for (int i=0;i<n;i++){
            arr[i]=s.charAt(i)-'a';
        }
        int l=1,r=n-1;
        int ans=0,start=-1;
        while (l<=r){
            int m=(l+r)/2;
            int pos=check(arr,m);
            if (pos!=-1){
                l=m+1;
                ans=m;
                start=pos;
            }else{
                r=m-1;
            }
        }
        return start==-1?"":s.substring(start,start+ans);
    }

    public int check(int[] arr,int m){
        long h1=0,h2=0;long jj1=1,jj2=1;
        for (int i=1;i<=m;i++){
            jj1=jj1*k1%mod1;
            if (jj1<0){
                jj1=jj1+mod1;
            }
        }
        for (int i=1;i<=m;i++){
            jj2=jj2*k2%mod2;
            if (jj2<0){
                jj2=jj2+mod2;
            }
        }
        for (int i=0;i<m;i++){
            h1=(h1*k1%mod1+arr[i])%mod1;
            if (h1<0){
                h1=h1+mod1;
            }
        }
        for (int i=0;i<m;i++){
            h2=(h2*k2%mod2+arr[i])%mod2;
            if (h2<0){
                h2=h2+mod2;
            }
        }
        Set<Long> set=new HashSet<>();
        set.add(h1*mod2+h2);
        for (int i=1;i<=arr.length-m;i++){
            h1=(h1*k1%mod1-arr[i-1]*jj1%mod1+arr[i+m-1])%mod1;
            if (h1<0){
                h1=h1+mod1;
            }
            h2=(h2*k2%mod2-arr[i-1]*jj2%mod2+arr[i+m-1])%mod2;
            if (h2<0){
                h2=h2+mod2;
            }
            if (set.contains(h1*mod2+h2)){
                return i;
            }else{
                set.add(h1*mod2+h2);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1044().longestDupSubstring("banana"));
    }
}
